322. Coin Change

不得不承認用動態規劃思考對於新手門檻真的頗高，不過這題實在太經典了，還是要練習一下。

// Question:
You are given coins of different denominations and a total amount of money amount. 
Write a function to compute the fewest number of coins that you need to make up that amount. 
If that amount of money cannot be made up by any combination of the coins, return -1.

Note:
You may assume that you have an infinite number of each kind of coin.

// Example 1:

Input: coins = [1, 2, 5], amount = 11
Output: 3 
Explanation: 11 = 5 + 5 + 1
Example 2:

Input: coins = [2], amount = 3
Output: -1

 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {
    
};

轉成圖片大家可能比較好懂到底要幹嘛 XD，其實題目就是說:
有不同面額的硬幣(數量無限)，我就以有 1, 2, 5 面額的硬幣為例，如何使用最少硬幣數湊成 11 ? 回傳硬幣數

一開始腦中可能像我一樣一片空白，不過先不要這麼貪心急著找答案，就先用最簡單想法來試試吧。

Think

極限值/特殊狀況

有可能有負的面額

大概會怎麼解

試想假如每種面額的硬幣都會用到
$1 + 10 = 11
$2 + 9 = 11
$5 + 6 = 11

接下來 10、9、6 又可以寫成兌換硬幣的組合，例如 10 = 5 + 5, 9 = 5 + 2 + 2, 6 = 5 + 1

總結以上，由於我們要找出最少數目，所以可以這樣想

f(11) = Math.min(1 + f(10), 1 + f(9), 1 + f(6))

其中 1 分別代表兌換面額 $1、$2、$5 的數量，而 f(n) 表示兌換 n 元所需最少數量。程式可以簡化成

f(11) = Math.min(f(10), f(9), f(6))

然後繼續跟一直重覆步驟直到找到 f(0)，f(0) 代表當下硬幣數量就可以代表需要的錢，
ex. f(5) = 1 + f(0), 1 代表 $5，只要 1 個 $5 就可以達到 amount 5

分解步驟

// 第一次
f(11) ＝ Math.min(1 + f(10), 1 + f(9), 1 + f(6))

// 第二次
f(10) = Math.min(1 + f(9), 1 + f(8), 1 + f(5)) 
f(9) = Math.min(1 + f(8), 1 + f(7), 1 + f(4))
f(6) = Math.min(1 + f(5), 1 + f(4), 1 + f(1))

// 第三次
f(9)) = Math.min(1 + f(8), 1 + f(7), 1 + f(4))
f(8) = Math.min(1 + f(7), 1 + f(6), 1 + f(3))
f(5) = Math.min(1 + f(4), 1 + f(3), 1 + f(0))  // 看到 f(0) 了
...

看到 f(0) 代表找到啦
amount 5 只有一種方式就是直接拿 1 個 $5，往回推算

f(5) = 1
f(10) = 1+ 1 = 2
f(11) = 1 + 2

所以答案 2 個 $5，1 個 $1，總共 3 個硬幣，答案就是 3

哪種資料結構解

思考了之後才會知道會往動態規劃方向走

完整程式碼

今天工作實在太忙，連在飛機上都還努力拼寫鐵人賽!

var coinChange = function(coins, amount) {
    if (!amount || !coins.length) {
        return 0;
    }
    
    let out = [0]; 
    let i, l;      
    let index = 1; 
    
    while (!out[amount]) {
        out[index] = Infinity; 
        for (i = 0, l = coins.length; i < l; i++) {           
            
            if (coins[i] <= index) {
                out[index] = Math.min(out[index], 1 + out[index - coins[i]]);
            } 
            
        }
        index++;   
    }
    
    return out[amount] === Infinity ? -1 : out[amount];
};

參考資料

• 演算法：如何思考動態規劃？

如有錯誤或需要改進的地方，拜託跟我說。
我會以最快速度修改，感謝您

歡迎追蹤我的部落格，除了技術文也會分享一些在矽谷工作的甘苦。